package com.tql.NodeTest;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Test {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(5);
        l1.add(2);
        l1.add(2);
        l1.add(1);
        l2.add(5);
        l2.add(1);
        l2.add(8);
        l2.add(4);
        ListNode listNode = middleNode(l1);
        listNode.print();


    }
    public static int fac(int n) {
        if (n == 1){
            return 1;
        } else {
            return n * fac(n-1);
        }
    }

    //链表合并问题
    //双向指针实现
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        else if(l2==null){
            return l1;
        }
        else if(l1.val<l2.val){
            l1.next= mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
//    //去除链表重复的节点
//    public static ListNode deleteDuplicates(ListNode head) {
//            int m=0;
//            if(head==null||head.next==null)return head;
//            head.next=deleteDuplicates(head.next);
//            m=10;
//            return head.val==head.next.val?head.next:head;
//    }
    //去除链表重复的节点2
    public static ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)return head;
        head.next=deleteDuplicates(head.next);
        return  head.val==head.next.val?head.next:head;
    }
    //Node节点
    public static class ListNode{
        int val;
        ListNode next;

        public ListNode() {
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public ListNode(int val) {
            this.val = val;
        }
        // 添加新的结点
        public void add(int newval) {
           ListNode newNode = new ListNode(newval);
            if(this.next == null)
                this.next = newNode;
            else
                this.next.add(newval);
        }
        // 打印链表
        public void print() {
            System.out.print(this.val);
            if(this.next != null)
            {
                System.out.print("-->");
                this.next.print();
            }
        }

    }
    public static boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            if(fast==null||fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }
    public static ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null){
            slow=slow.next;
           if(fast.next!=null){
               fast=fast.next.next;
           }else{
               return null;
           }
           if(fast==slow){
               ListNode pre=head;
               while(pre!=slow) {
                   pre = pre.next;
                   slow = slow.next;
               }
               return pre;
           }
        }
        return null;
    }
    //160. 相交链表
    /*
    * 解法1.hashmap
    * */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        HashSet<ListNode> params = new HashSet<ListNode>();
        ListNode temp=headA;
        while(temp!=null){
            params.add(temp);
            temp=temp.next;
        }
        temp=headB;
        while(temp!=null){
            boolean integer = params.contains(temp);
           if(integer){
                return  temp;
           }else{
               temp=temp.next;
           }
        }
        return null;
    }
    /*
     * 解法2.m-n O(n)
     * */
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        int m = 0,n=0;
        boolean flag;
        ListNode tempA=headA,tempB=headB;
        while(tempA!=null){
            m++;
            tempA=tempA.next;
        }
        while(tempB!=null){
            n++;
            tempB=tempB.next;
        }
        flag=m>=n?true:false;
        if(flag){
            tempA=headA;
            tempB=headB;
            for (int i = 0; i < m-n; i++) {
                tempA=tempA.next;
            }
        }else {
            tempA=headA;
            tempB=headB;
            for (int i = 0; i < n-m; i++) {
                tempB=tempB.next;
            }
        }
        while(tempA!=null&&tempB!=null){
            if(tempA==tempB){
                return tempA;
            }
            tempA=tempA.next;
            tempB=tempB.next;
        }
        return null;
    }
    /*
    * 206. 反转链表
    * */
    public static ListNode reverseList(ListNode head) {
       ListNode prev=null;
       ListNode temp=head;
       while(temp!=null){
           ListNode next = temp.next;
           temp.next=prev;
           prev=temp;
           temp=next;
       }
       return prev;
    }
    /*
    * 234. 回文链表
    * 解法1：数组，双指针
    * */
    public static boolean isPalindrome(ListNode head) {
        if(head==null){
            return false;
        }
        ArrayList<Integer> params = new ArrayList<Integer>();
        while(head!=null){
           params.add(head.val);
           head=head.next;
        }
        Integer[] contains = (Integer[])(params.toArray(new Integer[ params.size()]));
        int index=0;
        int last=contains.length-1;
        while(index<last){
            if(contains[index]!=contains[last]){
               return false;
            }else{
                index++;
                last--;
            }
        }
        return true;
    }
    /*
     * 234. 回文链表
     * 解法1：快慢指针翻转链表，比对
     * */
    public static boolean isPalindrome1(ListNode head) {
       if(head==null||head.next==null){
           return false;
       }
       ListNode fast=head;
       ListNode slow=head;
       while(fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }
        if(fast!=null){
            slow=slow.next;
        }
        slow = reverseList1(slow);
        fast=head;
        while(slow!=null){
            if(slow.val!=fast.val){
                return false;
            }
            slow=slow.next;
            fast=fast.next;
        }
        return true;
    }
    public static ListNode reverseList1(ListNode l1){
        if(l1==null){
            return null;
        }
        ListNode pre=null;
        ListNode temp=l1;
        while(temp!=null){
            ListNode next = temp.next;
            temp.next=pre;
            pre=temp;
            temp=next;
        }
        return pre;
    }
    /*
    * 876. 链表的中间结点
    * 解法1：根据长度
    * */
    public static ListNode middleNode(ListNode head) {
        int num=0;
        ListNode temp=head;
        while(temp!=null){
            num++;
            temp=temp.next;
        }
        for (int i = 0; i <num/2 ; i++) {
            head=head.next;
        }
        return head;
    }
    /*
     * 876. 链表的中间结点
     * 解法2：快慢指针
     * */
    public static ListNode middleNode1(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
       return slow;
    }
}
